package com.origin.niuke.dynamic;

/**
 * 编辑距离(一)
 * 算法：动态规划
 *
 * @author yezh
 * @date 2023/2/11 22:33
 */
public class NC196 {

    public int editDistance (String str1, String str2) {
        // write code here
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[2][n + 1];
        for (int i = 1; i <= n; i++) dp[0][i] = i;
        for (int i = 1; i <= m; i++) {
            int cur = i % 2, up = 1 - cur;
            dp[cur][0] = i;
            for (int j = 1; j <= n; j++) {
                int min = Math.min(dp[cur][j - 1], dp[up][j]);
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[up][j] = Math.min(
                        dp[up][j - 1], min + 1);
                else dp[up][j] = Math.min(dp[up][j - 1] + 1, min + 1);
            }
        }
        return dp[m % 2][n];
    }

}
